package com.example.lettcode._20240924;

import java.util.Arrays;

/*
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。


示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
 */
public class Shu_zu_cheng_ji {

    public static void main(String[] args) {
        int[] nums = {-1,1,0,-3,3};
        int[] ints = productExceptSelf3(nums);
        Arrays.stream(ints).forEach(System.out::println);
    }

    public static int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];

        left[0] = 1;
        for (int i = 1; i < left.length; i++) {
            left[i] = left[i-1] * nums[i-1];
        }

        right[right.length-1] = 1;
        for (int i = right.length-2; i >= 0; i--) {
            right[i] = right[i+1] * nums[i+1];
        }

        int[] anwers = new int[nums.length];

        for (int i = 0; i < anwers.length; i++) {
            anwers[i] = left[i] * right[i];
        }
        return anwers;
    }

    public static int[] productExceptSelf2(int[] nums) {
        int multResult = 1;
        int zeroCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
                continue;
            }
            multResult = multResult * nums[i];
        }

        int[] anwsers = new int[nums.length];
        for (int i = 0; i < anwsers.length; i++) {
            if (zeroCount > 1) {
                anwsers[i] = 0;
                continue;
            }
            if (zeroCount == 1) {
                if (nums[i] == 0) {
                    anwsers[i] = multResult;
                } else {
                    anwsers[i] = 0;
                }
                continue;
            }
            anwsers[i] = multResult / nums[i];
        }
        return anwsers;
    }

    /**
     * 获取每一个元素左右两边的数据的乘积数组
     * @param nums
     * @return
     */
    public static int[] productExceptSelf3(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];

        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = nums[i-1] * left[i-1];
        }

        right[n-1] = 1;
        for (int i = n - 2; i >=0 ; i--) {
            right[i] = nums[i+1] * right[i+1];
        }

        int[] anwers = new int[n];
        for (int i = 0; i < n; i++) {
            anwers[i] = left[i] * right[i];
        }
        return anwers;
    }
}
